package com.shm.leetcode;

/**
 * 992. K 个不同整数的子数组
 * 给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。
 *
 * （例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）
 *
 * 返回 A 中好子数组的数目。
 *
 *
 *
 * 示例 1：
 *
 * 输入：A = [1,2,1,2,3], K = 2
 * 输出：7
 * 解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
 * 示例 2：
 *
 * 输入：A = [1,2,1,3,4], K = 3
 * 输出：3
 * 解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].
 *
 *
 * 提示：
 *
 * 1 <= A.length <= 20000
 * 1 <= A[i] <= A.length
 * 1 <= K <= A.length
 * @author SHM
 */
public class SubarraysWithKDistinct {
    /**
     * 最初直觉使用双指针算法遇到的问题
     * 对于一个固定的左边界来说，满足「恰好存在 K 个不同整数的子区间」的右边界 不唯一，且形成区间。
     *
     * 示例 1：左边界固定的时候，恰好存在 22 个不同整数的子区间为 [1,2],[1,2,1],[1,2,1,2][1,2],[1,2,1],[1,2,1,2] ，总数为 33。其值为下标 3 - 1 + 13−1+1，即区间 [1..3][1..3] 的长度。
     *
     *
     *
     * 须要找到左边界固定的情况下，满足「恰好存在 K 个不同整数的子区间」最小右边界和最大右边界。对比以前我们做过的，使用双指针解决的问题的问法基本都会出现「最小」、「最大」这样的字眼。
     *
     * 76. 最小覆盖子串；
     * 209. 长度最小的子数组；
     * 159. 至多包含两个不同字符的最长子串；
     * 424. 替换后的最长重复字符。
     * 把原问题转换成为容易求解的问题
     * 把「恰好」改成「最多」就可以使用双指针一前一后交替向右的方法完成，这是因为 对于每一个确定的左边界，最多包含 KK 种不同整数的右边界是唯一确定的，并且在左边界向右移动的过程中，右边界或者在原来的地方，或者在原来地方的右边。
     *
     * 而「最多存在 KK 个不同整数的子区间的个数」与「恰好存在 K 个不同整数的子区间的个数」的差恰好等于「最多存在 K - 1K−1 个不同整数的子区间的个数」。
     *
     *
     *
     * 因为原问题就转换成为求解「最多存在 KK 个不同整数的子区间的个数」与 「最多存在 K - 1K−1 个不同整数的子区间的个数」，它们其实是一个问题。
     *
     * 方法：双指针（滑动窗口）
     * 实现函数 atMostWithKDistinct(A, K) ，表示「最多存在 KK 个不同整数的子区间的个数」。于是 atMostWithKDistinct(A, K) - atMostWithKDistinct(A, K - 1) 即为所求。
     *
     * 复杂度分析：
     *
     * 时间复杂度：O(N)O(N)，这里 NN 是输入数组的长度；
     * 空间复杂度：O(N)O(N)，使用了常数个变量、频数数组的长度为 NN。
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/subarrays-with-k-different-integers/solution/k-ge-bu-tong-zheng-shu-de-zi-shu-zu-by-l-ud34/
     * @param A
     * @param K
     * @return
     */
    public int subarraysWithKDistinct(int[] A, int K) {
        return atMostKDist(A,K)-atMostKDist(A,K-1);
    }

    /**
     * 最多包含 K 个不同整数的子区间的个数
     * @param A
     * @param k
     * @return
     */
    int atMostKDist(int[] A,int k){
        int n = A.length;
        int left =0,right=0;
        int[] freq = new int[n+1];
        // [left, right) 里不同整数的个数
        int count = 0;
        int res = 0;
        // [left, right) 包含不同整数的个数小于等于 K
        while(right<n){
            if(freq[A[right]]==0){
                count++;
            }
            freq[A[right]]++;
            right++;
            while(count>k){
                freq[A[left]]--;
                if(freq[A[left]]==0){
                    count--;
                }
                left++;
            }
            // [left, right) 区间的长度就是对结果的贡献
            res+=right-left;
        }
        return res;
    }
}
